'''
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity. 
'''

import Queue

# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class ListNodeX(ListNode):
    def __init__(self, x):
        ListNode.__init__(self, x)
    def __cmp__(self, other):
        return cmp(self.val, other.val)

class Solution:
    # @param {ListNode[]} lists
    # @return {ListNode}
    def mergeKLists(self, lists):
        '''
        :type lists: ListNode[]
        '''

        pq = Queue.PriorityQueue()
        
        for l in lists:
            if l:
                node = ListNodeX(l.val)
                node.next = l.next
                pq.put_nowait(node)

        ans = ListNode(0)
        cur = ans
        while not pq.empty():
            top = pq.get(False)
            cur.next = ListNode(top.val)
            top = top.next
            cur = cur.next

            if top:
                node = ListNodeX(top.val)
                node.next = top.next
                pq.put_nowait(node)
        
        return ans.next

